home *** CD-ROM | disk | FTP | other *** search
/ Sprite 1984 - 1993 / Sprite 1984 - 1993.iso / src / cmds / update / RCS / regexp.c,v < prev    next >
Encoding:
Text File  |  1992-01-28  |  27.4 KB  |  1,252 lines
  1. head     1.1;
  2. branch   ;
  3. access   ;
  4. symbols  ;
  5. locks    ; strict;
  6. comment  @ * @;
  7.  
  8.  
  9. 1.1
  10. date     92.01.27.22.22.58;  author jhh;  state Exp;
  11. branches ;
  12. next     ;
  13.  
  14.  
  15. desc
  16. @@
  17.  
  18.  
  19.  
  20. 1.1
  21. log
  22. @Initial revision
  23. @
  24. text
  25. @/*
  26.  * regcomp and regexec -- regsub and regerror are elsewhere
  27.  *
  28.  *    Copyright (c) 1986 by University of Toronto.
  29.  *    Written by Henry Spencer.  Not derived from licensed software.
  30.  *
  31.  *    Permission is granted to anyone to use this software for any
  32.  *    purpose on any computer system, and to redistribute it freely,
  33.  *    subject to the following restrictions:
  34.  *
  35.  *    1. The author is not responsible for the consequences of use of
  36.  *        this software, no matter how awful, even if they arise
  37.  *        from defects in it.
  38.  *
  39.  *    2. The origin of this software must not be misrepresented, either
  40.  *        by explicit claim or by omission.
  41.  *
  42.  *    3. Altered versions must be plainly marked as such, and must not
  43.  *        be misrepresented as being the original software.
  44.  *
  45.  * Beware that some of this code is subtly aware of the way operator
  46.  * precedence is structured in regular expressions.  Serious changes in
  47.  * regular-expression syntax might require a total rethink.
  48.  */
  49. #include <sprite.h>
  50. #include <regexp.h>
  51.  
  52. /*
  53.  * The "internal use only" fields in regexp.h are present to pass info from
  54.  * compile to execute that permits the execute phase to run lots faster on
  55.  * simple cases.  They are:
  56.  *
  57.  * regstart    char that must begin a match; '\0' if none obvious
  58.  * reganch    is the match anchored (at beginning-of-line only)?
  59.  * regmust    string (pointer into program) that match must include, or NULL
  60.  * regmlen    length of regmust string
  61.  *
  62.  * Regstart and reganch permit very fast decisions on suitable starting points
  63.  * for a match, cutting down the work a lot.  Regmust permits fast rejection
  64.  * of lines that cannot possibly match.  The regmust tests are costly enough
  65.  * that regcomp() supplies a regmust only if the r.e. contains something
  66.  * potentially expensive (at present, the only such thing detected is * or +
  67.  * at the start of the r.e., which can involve a lot of backup).  Regmlen is
  68.  * supplied because the test in regexec() needs it and regcomp() is computing
  69.  * it anyway.
  70.  */
  71.  
  72. /*
  73.  * Structure for regexp "program".  This is essentially a linear encoding
  74.  * of a nondeterministic finite-state machine (aka syntax charts or
  75.  * "railroad normal form" in parsing technology).  Each node is an opcode
  76.  * plus a "next" pointer, possibly plus an operand.  "Next" pointers of
  77.  * all nodes except BRANCH implement concatenation; a "next" pointer with
  78.  * a BRANCH on both ends of it is connecting two alternatives.  (Here we
  79.  * have one of the subtle syntax dependencies:  an individual BRANCH (as
  80.  * opposed to a collection of them) is never concatenated with anything
  81.  * because of operator precedence.)  The operand of some types of node is
  82.  * a literal string; for others, it is a node leading into a sub-FSM.  In
  83.  * particular, the operand of a BRANCH node is the first node of the branch.
  84.  * (NB this is *not* a tree structure:  the tail of the branch connects
  85.  * to the thing following the set of BRANCHes.)  The opcodes are:
  86.  */
  87.  
  88. /* definition    number    opnd?    meaning */
  89. #define    END    0    /* no    End of program. */
  90. #define    BOL    1    /* no    Match "" at beginning of line. */
  91. #define    EOL    2    /* no    Match "" at end of line. */
  92. #define    ANY    3    /* no    Match any one character. */
  93. #define    ANYOF    4    /* str    Match any character in this string. */
  94. #define    ANYBUT    5    /* str    Match any character not in this string. */
  95. #define    BRANCH    6    /* node    Match this alternative, or the next... */
  96. #define    BACK    7    /* no    Match "", "next" ptr points backward. */
  97. #define    EXACTLY    8    /* str    Match this string. */
  98. #define    NOTHING    9    /* no    Match empty string. */
  99. #define    STAR    10    /* node    Match this (simple) thing 0 or more times. */
  100. #define    PLUS    11    /* node    Match this (simple) thing 1 or more times. */
  101. #define    OPEN    20    /* no    Mark this point in input as start of #n. */
  102.             /*    OPEN+1 is number 1, etc. */
  103. #define    CLOSE    30    /* no    Analogous to OPEN. */
  104.  
  105. /*
  106.  * Opcode notes:
  107.  *
  108.  * BRANCH    The set of branches constituting a single choice are hooked
  109.  *        together with their "next" pointers, since precedence prevents
  110.  *        anything being concatenated to any individual branch.  The
  111.  *        "next" pointer of the last BRANCH in a choice points to the
  112.  *        thing following the whole choice.  This is also where the
  113.  *        final "next" pointer of each individual branch points; each
  114.  *        branch starts with the operand node of a BRANCH node.
  115.  *
  116.  * BACK        Normal "next" pointers all implicitly point forward; BACK
  117.  *        exists to make loop structures possible.
  118.  *
  119.  * STAR,PLUS    '?', and complex '*' and '+', are implemented as circular
  120.  *        BRANCH structures using BACK.  Simple cases (one character
  121.  *        per match) are implemented with STAR and PLUS for speed
  122.  *        and to minimize recursive plunges.
  123.  *
  124.  * OPEN,CLOSE    ...are numbered at compile time.
  125.  */
  126.  
  127. /*
  128.  * A node is one char of opcode followed by two chars of "next" pointer.
  129.  * "Next" pointers are stored as two 8-bit pieces, high order first.  The
  130.  * value is a positive offset from the opcode of the node containing it.
  131.  * An operand, if any, simply follows the node.  (Note that much of the
  132.  * code generation knows about this implicit relationship.)
  133.  *
  134.  * Using two bytes for the "next" pointer is vast overkill for most things,
  135.  * but allows patterns to get big without disasters.
  136.  */
  137. #define    OP(p)    (*(p))
  138. #define    NEXT(p)    (((*((p)+1)&0377)<<8) + (*((p)+2)&0377))
  139. #define    OPERAND(p)    ((p) + 3)
  140.  
  141. /*
  142.  * See regmagic.h for one further detail of program structure.
  143.  */
  144.  
  145.  
  146. /*
  147.  * Utility definitions.
  148.  */
  149. #ifndef CHARBITS
  150. #define    UCHARAT(p)    ((int)*(unsigned char *)(p))
  151. #else
  152. #define    UCHARAT(p)    ((int)*(p)&CHARBITS)
  153. #endif
  154.  
  155. #define    FAIL(m)    { regerror(m); return(NULL); }
  156. #define    ISMULT(c)    ((c) == '*' || (c) == '+' || (c) == '?')
  157. #define    META    "^$.[()|?+*\\"
  158.  
  159. /*
  160.  * Flags to be passed up and down.
  161.  */
  162. #define    HASWIDTH    01    /* Known never to match null string. */
  163. #define    SIMPLE        02    /* Simple enough to be STAR/PLUS operand. */
  164. #define    SPSTART        04    /* Starts with * or +. */
  165. #define    WORST        0    /* Worst case. */
  166.  
  167. /*
  168.  * Global work variables for regcomp().
  169.  */
  170. static char *regparse;        /* Input-scan pointer. */
  171. static int regnpar;        /* () count. */
  172. static char regdummy;
  173. static char *regcode;        /* Code-emit pointer; ®dummy = don't. */
  174. static long regsize;        /* Code size. */
  175.  
  176. /*
  177.  * The first byte of the regexp internal "program" is actually this magic
  178.  * number; the start node begins in the second byte.
  179.  */
  180. #define    MAGIC    0234
  181.  
  182.  
  183. /*
  184.  * Forward declarations for regcomp()'s friends.
  185.  */
  186. #ifndef STATIC
  187. #define    STATIC    static
  188. #endif
  189. STATIC char *reg();
  190. STATIC char *regbranch();
  191. STATIC char *regpiece();
  192. STATIC char *regatom();
  193. STATIC char *regnode();
  194. STATIC char *regnext();
  195. STATIC void regc();
  196. STATIC void reginsert();
  197. STATIC void regtail();
  198. STATIC void regoptail();
  199. #ifdef STRCSPN
  200. STATIC int strcspn();
  201. #endif
  202.  
  203. /*
  204.  - regcomp - compile a regular expression into internal code
  205.  *
  206.  * We can't allocate space until we know how big the compiled form will be,
  207.  * but we can't compile it (and thus know how big it is) until we've got a
  208.  * place to put the code.  So we cheat:  we compile it twice, once with code
  209.  * generation turned off and size counting turned on, and once "for real".
  210.  * This also means that we don't allocate space until we are sure that the
  211.  * thing really will compile successfully, and we never have to move the
  212.  * code and thus invalidate pointers into it.  (Note that it has to be in
  213.  * one piece because free() must be able to free it all.)
  214.  *
  215.  * Beware that the optimization-preparation code in here knows about some
  216.  * of the structure of the compiled regexp.
  217.  */
  218. regexp *
  219. regcomp(exp)
  220. char *exp;
  221. {
  222.     register regexp *r;
  223.     register char *scan;
  224.     register char *longest;
  225.     register int len;
  226.     int flags;
  227.  
  228.     if (exp == NULL)
  229.         FAIL("NULL argument");
  230.  
  231.     /* First pass: determine size, legality. */
  232.     regparse = exp;
  233.     regnpar = 1;
  234.     regsize = 0L;
  235.     regcode = ®dummy;
  236.     regc(MAGIC);
  237.     if (reg(0, &flags) == NULL)
  238.         return(NULL);
  239.  
  240.     /* Small enough for pointer-storage convention? */
  241.     if (regsize >= 32767L)        /* Probably could be 65535L. */
  242.         FAIL("regexp too big");
  243.  
  244.     /* Allocate space. */
  245.     r = (regexp *)malloc(sizeof(regexp) + (unsigned)regsize);
  246.     if (r == NULL)
  247.         FAIL("out of space");
  248.  
  249.     /* Second pass: emit code. */
  250.     regparse = exp;
  251.     regnpar = 1;
  252.     regcode = r->program;
  253.     regc(MAGIC);
  254.     if (reg(0, &flags) == NULL)
  255.         return(NULL);
  256.  
  257.     /* Dig out information for optimizations. */
  258.     r->regstart = '\0';    /* Worst-case defaults. */
  259.     r->reganch = 0;
  260.     r->regmust = NULL;
  261.     r->regmlen = 0;
  262.     scan = r->program+1;            /* First BRANCH. */
  263.     if (OP(regnext(scan)) == END) {        /* Only one top-level choice. */
  264.         scan = OPERAND(scan);
  265.  
  266.         /* Starting-point info. */
  267.         if (OP(scan) == EXACTLY)
  268.             r->regstart = *OPERAND(scan);
  269.         else if (OP(scan) == BOL)
  270.             r->reganch++;
  271.  
  272.         /*
  273.          * If there's something expensive in the r.e., find the
  274.          * longest literal string that must appear and make it the
  275.          * regmust.  Resolve ties in favor of later strings, since
  276.          * the regstart check works with the beginning of the r.e.
  277.          * and avoiding duplication strengthens checking.  Not a
  278.          * strong reason, but sufficient in the absence of others.
  279.          */
  280.         if (flags&SPSTART) {
  281.             longest = NULL;
  282.             len = 0;
  283.             for (; scan != NULL; scan = regnext(scan))
  284.                 if (OP(scan) == EXACTLY && strlen(OPERAND(scan)) >= len) {
  285.                     longest = OPERAND(scan);
  286.                     len = strlen(OPERAND(scan));
  287.                 }
  288.             r->regmust = longest;
  289.             r->regmlen = len;
  290.         }
  291.     }
  292.  
  293.     return(r);
  294. }
  295.  
  296. /*
  297.  - reg - regular expression, i.e. main body or parenthesized thing
  298.  *
  299.  * Caller must absorb opening parenthesis.
  300.  *
  301.  * Combining parenthesis handling with the base level of regular expression
  302.  * is a trifle forced, but the need to tie the tails of the branches to what
  303.  * follows makes it hard to avoid.
  304.  */
  305. static char *
  306. reg(paren, flagp)
  307. int paren;            /* Parenthesized? */
  308. int *flagp;
  309. {
  310.     register char *ret;
  311.     register char *br;
  312.     register char *ender;
  313.     register int parno = 0;
  314.     int flags;
  315.  
  316.     *flagp = HASWIDTH;    /* Tentatively. */
  317.  
  318.     /* Make an OPEN node, if parenthesized. */
  319.     if (paren) {
  320.         if (regnpar >= NSUBEXP)
  321.             FAIL("too many ()");
  322.         parno = regnpar;
  323.         regnpar++;
  324.         ret = regnode(OPEN+parno);
  325.     } else
  326.         ret = NULL;
  327.  
  328.     /* Pick up the branches, linking them together. */
  329.     br = regbranch(&flags);
  330.     if (br == NULL)
  331.         return(NULL);
  332.     if (ret != NULL)
  333.         regtail(ret, br);    /* OPEN -> first. */
  334.     else
  335.         ret = br;
  336.     if (!(flags&HASWIDTH))
  337.         *flagp &= ~HASWIDTH;
  338.     *flagp |= flags&SPSTART;
  339.     while (*regparse == '|') {
  340.         regparse++;
  341.         br = regbranch(&flags);
  342.         if (br == NULL)
  343.             return(NULL);
  344.         regtail(ret, br);    /* BRANCH -> BRANCH. */
  345.         if (!(flags&HASWIDTH))
  346.             *flagp &= ~HASWIDTH;
  347.         *flagp |= flags&SPSTART;
  348.     }
  349.  
  350.     /* Make a closing node, and hook it on the end. */
  351.     ender = regnode((paren) ? CLOSE+parno : END);    
  352.     regtail(ret, ender);
  353.  
  354.     /* Hook the tails of the branches to the closing node. */
  355.     for (br = ret; br != NULL; br = regnext(br))
  356.         regoptail(br, ender);
  357.  
  358.     /* Check for proper termination. */
  359.     if (paren && *regparse++ != ')') {
  360.         FAIL("unmatched ()");
  361.     } else if (!paren && *regparse != '\0') {
  362.         if (*regparse == ')') {
  363.             FAIL("unmatched ()");
  364.         } else
  365.             FAIL("junk on end");    /* "Can't happen". */
  366.         /* NOTREACHED */
  367.     }
  368.  
  369.     return(ret);
  370. }
  371.  
  372. /*
  373.  - regbranch - one alternative of an | operator
  374.  *
  375.  * Implements the concatenation operator.
  376.  */
  377. static char *
  378. regbranch(flagp)
  379. int *flagp;
  380. {
  381.     register char *ret;
  382.     register char *chain;
  383.     register char *latest;
  384.     int flags;
  385.  
  386.     *flagp = WORST;        /* Tentatively. */
  387.  
  388.     ret = regnode(BRANCH);
  389.     chain = NULL;
  390.     while (*regparse != '\0' && *regparse != '|' && *regparse != ')') {
  391.         latest = regpiece(&flags);
  392.         if (latest == NULL)
  393.             return(NULL);
  394.         *flagp |= flags&HASWIDTH;
  395.         if (chain == NULL)    /* First piece. */
  396.             *flagp |= flags&SPSTART;
  397.         else
  398.             regtail(chain, latest);
  399.         chain = latest;
  400.     }
  401.     if (chain == NULL)    /* Loop ran zero times. */
  402.         (void) regnode(NOTHING);
  403.  
  404.     return(ret);
  405. }
  406.  
  407. /*
  408.  - regpiece - something followed by possible [*+?]
  409.  *
  410.  * Note that the branching code sequences used for ? and the general cases
  411.  * of * and + are somewhat optimized:  they use the same NOTHING node as
  412.  * both the endmarker for their branch list and the body of the last branch.
  413.  * It might seem that this node could be dispensed with entirely, but the
  414.  * endmarker role is not redundant.
  415.  */
  416. static char *
  417. regpiece(flagp)
  418. int *flagp;
  419. {
  420.     register char *ret;
  421.     register char op;
  422.     register char *next;
  423.     int flags;
  424.  
  425.     ret = regatom(&flags);
  426.     if (ret == NULL)
  427.         return(NULL);
  428.  
  429.     op = *regparse;
  430.     if (!ISMULT(op)) {
  431.         *flagp = flags;
  432.         return(ret);
  433.     }
  434.  
  435.     if (!(flags&HASWIDTH) && op != '?')
  436.         FAIL("*+ operand could be empty");
  437.     *flagp = (op != '+') ? (WORST|SPSTART) : (WORST|HASWIDTH);
  438.  
  439.     if (op == '*' && (flags&SIMPLE))
  440.         reginsert(STAR, ret);
  441.     else if (op == '*') {
  442.         /* Emit x* as (x&|), where & means "self". */
  443.         reginsert(BRANCH, ret);            /* Either x */
  444.         regoptail(ret, regnode(BACK));        /* and loop */
  445.         regoptail(ret, ret);            /* back */
  446.         regtail(ret, regnode(BRANCH));        /* or */
  447.         regtail(ret, regnode(NOTHING));        /* null. */
  448.     } else if (op == '+' && (flags&SIMPLE))
  449.         reginsert(PLUS, ret);
  450.     else if (op == '+') {
  451.         /* Emit x+ as x(&|), where & means "self". */
  452.         next = regnode(BRANCH);            /* Either */
  453.         regtail(ret, next);
  454.         regtail(regnode(BACK), ret);        /* loop back */
  455.         regtail(next, regnode(BRANCH));        /* or */
  456.         regtail(ret, regnode(NOTHING));        /* null. */
  457.     } else if (op == '?') {
  458.         /* Emit x? as (x|) */
  459.         reginsert(BRANCH, ret);            /* Either x */
  460.         regtail(ret, regnode(BRANCH));        /* or */
  461.         next = regnode(NOTHING);        /* null. */
  462.         regtail(ret, next);
  463.         regoptail(ret, next);
  464.     }
  465.     regparse++;
  466.     if (ISMULT(*regparse))
  467.         FAIL("nested *?+");
  468.  
  469.     return(ret);
  470. }
  471.  
  472. /*
  473.  - regatom - the lowest level
  474.  *
  475.  * Optimization:  gobbles an entire sequence of ordinary characters so that
  476.  * it can turn them into a single node, which is smaller to store and
  477.  * faster to run.  Backslashed characters are exceptions, each becoming a
  478.  * separate node; the code is simpler that way and it's not worth fixing.
  479.  */
  480. static char *
  481. regatom(flagp)
  482. int *flagp;
  483. {
  484.     register char *ret;
  485.     int flags;
  486.  
  487.     *flagp = WORST;        /* Tentatively. */
  488.  
  489.     switch (*regparse++) {
  490.     case '^':
  491.         ret = regnode(BOL);
  492.         break;
  493.     case '$':
  494.         ret = regnode(EOL);
  495.         break;
  496.     case '.':
  497.         ret = regnode(ANY);
  498.         *flagp |= HASWIDTH|SIMPLE;
  499.         break;
  500.     case '[': {
  501.             register int clss;
  502.             register int classend;
  503.  
  504.             if (*regparse == '^') {    /* Complement of range. */
  505.                 ret = regnode(ANYBUT);
  506.                 regparse++;
  507.             } else
  508.                 ret = regnode(ANYOF);
  509.             if (*regparse == ']' || *regparse == '-')
  510.                 regc(*regparse++);
  511.             while (*regparse != '\0' && *regparse != ']') {
  512.                 if (*regparse == '-') {
  513.                     regparse++;
  514.                     if (*regparse == ']' || *regparse == '\0')
  515.                         regc('-');
  516.                     else {
  517.                         clss = UCHARAT(regparse-2)+1;
  518.                         classend = UCHARAT(regparse);
  519.                         if (clss > classend+1)
  520.                             FAIL("invalid [] range");
  521.                         for (; clss <= classend; clss++)
  522.                             regc(clss);
  523.                         regparse++;
  524.                     }
  525.                 } else
  526.                     regc(*regparse++);
  527.             }
  528.             regc('\0');
  529.             if (*regparse != ']')
  530.                 FAIL("unmatched []");
  531.             regparse++;
  532.             *flagp |= HASWIDTH|SIMPLE;
  533.         }
  534.         break;
  535.     case '(':
  536.         ret = reg(1, &flags);
  537.         if (ret == NULL)
  538.             return(NULL);
  539.         *flagp |= flags&(HASWIDTH|SPSTART);
  540.         break;
  541.     case '\0':
  542.     case '|':
  543.     case ')':
  544.         FAIL("internal urp");    /* Supposed to be caught earlier. */
  545.         /* NOTREACHED */
  546.         break;
  547.     case '?':
  548.     case '+':
  549.     case '*':
  550.         FAIL("?+* follows nothing");
  551.         /* NOTREACHED */
  552.         break;
  553.     case '\\':
  554.         if (*regparse == '\0')
  555.             FAIL("trailing \\");
  556.         ret = regnode(EXACTLY);
  557.         regc(*regparse++);
  558.         regc('\0');
  559.         *flagp |= HASWIDTH|SIMPLE;
  560.         break;
  561.     default: {
  562.             register int len;
  563.             register char ender;
  564.  
  565.             regparse--;
  566.             len = strcspn(regparse, META);
  567.             if (len <= 0)
  568.                 FAIL("internal disaster");
  569.             ender = *(regparse+len);
  570.             if (len > 1 && ISMULT(ender))
  571.                 len--;        /* Back off clear of ?+* operand. */
  572.             *flagp |= HASWIDTH;
  573.             if (len == 1)
  574.                 *flagp |= SIMPLE;
  575.             ret = regnode(EXACTLY);
  576.             while (len > 0) {
  577.                 regc(*regparse++);
  578.                 len--;
  579.             }
  580.             regc('\0');
  581.         }
  582.         break;
  583.     }
  584.  
  585.     return(ret);
  586. }
  587.  
  588. /*
  589.  - regnode - emit a node
  590.  */
  591. static char *            /* Location. */
  592. regnode(op)
  593. char op;
  594. {
  595.     register char *ret;
  596.     register char *ptr;
  597.  
  598.     ret = regcode;
  599.     if (ret == ®dummy) {
  600.         regsize += 3;
  601.         return(ret);
  602.     }
  603.  
  604.     ptr = ret;
  605.     *ptr++ = op;
  606.     *ptr++ = '\0';        /* Null "next" pointer. */
  607.     *ptr++ = '\0';
  608.     regcode = ptr;
  609.  
  610.     return(ret);
  611. }
  612.  
  613. /*
  614.  - regc - emit (if appropriate) a byte of code
  615.  */
  616. static void
  617. regc(b)
  618. char b;
  619. {
  620.     if (regcode != ®dummy)
  621.         *regcode++ = b;
  622.     else
  623.         regsize++;
  624. }
  625.  
  626. /*
  627.  - reginsert - insert an operator in front of already-emitted operand
  628.  *
  629.  * Means relocating the operand.
  630.  */
  631. static void
  632. reginsert(op, opnd)
  633. char op;
  634. char *opnd;
  635. {
  636.     register char *src;
  637.     register char *dst;
  638.     register char *place;
  639.  
  640.     if (regcode == ®dummy) {
  641.         regsize += 3;
  642.         return;
  643.     }
  644.  
  645.     src = regcode;
  646.     regcode += 3;
  647.     dst = regcode;
  648.     while (src > opnd)
  649.         *--dst = *--src;
  650.  
  651.     place = opnd;        /* Op node, where operand used to be. */
  652.     *place++ = op;
  653.     *place++ = '\0';
  654.     *place++ = '\0';
  655. }
  656.  
  657. /*
  658.  - regtail - set the next-pointer at the end of a node chain
  659.  */
  660. static void
  661. regtail(p, val)
  662. char *p;
  663. char *val;
  664. {
  665.     register char *scan;
  666.     register char *temp;
  667.     register int offset;
  668.  
  669.     if (p == ®dummy)
  670.         return;
  671.  
  672.     /* Find last node. */
  673.     scan = p;
  674.     for (;;) {
  675.         temp = regnext(scan);
  676.         if (temp == NULL)
  677.             break;
  678.         scan = temp;
  679.     }
  680.  
  681.     if (OP(scan) == BACK)
  682.         offset = scan - val;
  683.     else
  684.         offset = val - scan;
  685.     *(scan+1) = (offset>>8)&0377;
  686.     *(scan+2) = offset&0377;
  687. }
  688.  
  689. /*
  690.  - regoptail - regtail on operand of first argument; nop if operandless
  691.  */
  692. static void
  693. regoptail(p, val)
  694. char *p;
  695. char *val;
  696. {
  697.     /* "Operandless" and "op != BRANCH" are synonymous in practice. */
  698.     if (p == NULL || p == ®dummy || OP(p) != BRANCH)
  699.         return;
  700.     regtail(OPERAND(p), val);
  701. }
  702.  
  703. /*
  704.  * regexec and friends
  705.  */
  706.  
  707. /*
  708.  * Global work variables for regexec().
  709.  */
  710. static char *reginput;        /* String-input pointer. */
  711. static char *regbol;        /* Beginning of input, for ^ check. */
  712. static char **regstartp;    /* Pointer to startp array. */
  713. static char **regendp;        /* Ditto for endp. */
  714.  
  715. /*
  716.  * Forwards.
  717.  */
  718. STATIC int regtry();
  719. STATIC int regmatch();
  720. STATIC int regrepeat();
  721.  
  722. #ifdef DEBUG
  723. int regnarrate = 0;
  724. void regdump();
  725. STATIC char *regprop();
  726. #endif
  727.  
  728. /*
  729.  - regexec - match a regexp against a string
  730.  */
  731. int
  732. regexec(prog, string)
  733. register regexp *prog;
  734. register char *string;
  735. {
  736.     register char *s;
  737.     extern char *strchr();
  738.  
  739.     /* Be paranoid... */
  740.     if (prog == NULL || string == NULL) {
  741.         regerror("NULL parameter");
  742.         return(0);
  743.     }
  744.  
  745.     /* Check validity of program. */
  746.     if (UCHARAT(prog->program) != MAGIC) {
  747.         regerror("corrupted program");
  748.         return(0);
  749.     }
  750.  
  751.     /* If there is a "must appear" string, look for it. */
  752.     if (prog->regmust != NULL) {
  753.         s = string;
  754.         while ((s = strchr(s, prog->regmust[0])) != NULL) {
  755.             if (strncmp(s, prog->regmust, prog->regmlen) == 0)
  756.                 break;    /* Found it. */
  757.             s++;
  758.         }
  759.         if (s == NULL)    /* Not present. */
  760.             return(0);
  761.     }
  762.  
  763.     /* Mark beginning of line for ^ . */
  764.     regbol = string;
  765.  
  766.     /* Simplest case:  anchored match need be tried only once. */
  767.     if (prog->reganch)
  768.         return(regtry(prog, string));
  769.  
  770.     /* Messy cases:  unanchored match. */
  771.     s = string;
  772.     if (prog->regstart != '\0')
  773.         /* We know what char it must start with. */
  774.         while ((s = strchr(s, prog->regstart)) != NULL) {
  775.             if (regtry(prog, s))
  776.                 return(1);
  777.             s++;
  778.         }
  779.     else
  780.         /* We don't -- general case. */
  781.         do {
  782.             if (regtry(prog, s))
  783.                 return(1);
  784.         } while (*s++ != '\0');
  785.  
  786.     /* Failure. */
  787.     return(0);
  788. }
  789.  
  790. /*
  791.  - regtry - try match at specific point
  792.  */
  793. static int            /* 0 failure, 1 success */
  794. regtry(prog, string)
  795. regexp *prog;
  796. char *string;
  797. {
  798.     register int i;
  799.     register char **sp;
  800.     register char **ep;
  801.  
  802.     reginput = string;
  803.     regstartp = prog->startp;
  804.     regendp = prog->endp;
  805.  
  806.     sp = prog->startp;
  807.     ep = prog->endp;
  808.     for (i = NSUBEXP; i > 0; i--) {
  809.         *sp++ = NULL;
  810.         *ep++ = NULL;
  811.     }
  812.     if (regmatch(prog->program + 1)) {
  813.         prog->startp[0] = string;
  814.         prog->endp[0] = reginput;
  815.         return(1);
  816.     } else
  817.         return(0);
  818. }
  819.  
  820. /*
  821.  - regmatch - main matching routine
  822.  *
  823.  * Conceptually the strategy is simple:  check to see whether the current
  824.  * node matches, call self recursively to see whether the rest matches,
  825.  * and then act accordingly.  In practice we make some effort to avoid
  826.  * recursion, in particular by going through "ordinary" nodes (that don't
  827.  * need to know whether the rest of the match failed) by a loop instead of
  828.  * by recursion.
  829.  */
  830. static int            /* 0 failure, 1 success */
  831. regmatch(prog)
  832. char *prog;
  833. {
  834.     register char *scan;    /* Current node. */
  835.     char *next;        /* Next node. */
  836.     extern char *strchr();
  837.  
  838.     scan = prog;
  839. #ifdef DEBUG
  840.     if (scan != NULL && regnarrate)
  841.         fprintf(stderr, "%s(\n", regprop(scan));
  842. #endif
  843.     while (scan != NULL) {
  844. #ifdef DEBUG
  845.         if (regnarrate)
  846.             fprintf(stderr, "%s...\n", regprop(scan));
  847. #endif
  848.         next = regnext(scan);
  849.  
  850.         switch (OP(scan)) {
  851.         case BOL:
  852.             if (reginput != regbol)
  853.                 return(0);
  854.             break;
  855.         case EOL:
  856.             if (*reginput != '\0')
  857.                 return(0);
  858.             break;
  859.         case ANY:
  860.             if (*reginput == '\0')
  861.                 return(0);
  862.             reginput++;
  863.             break;
  864.         case EXACTLY: {
  865.                 register int len;
  866.                 register char *opnd;
  867.  
  868.                 opnd = OPERAND(scan);
  869.                 /* Inline the first character, for speed. */
  870.                 if (*opnd != *reginput)
  871.                     return(0);
  872.                 len = strlen(opnd);
  873.                 if (len > 1 && strncmp(opnd, reginput, len) != 0)
  874.                     return(0);
  875.                 reginput += len;
  876.             }
  877.             break;
  878.         case ANYOF:
  879.              if (*reginput == '\0' || strchr(OPERAND(scan), *reginput) == NULL)
  880.                 return(0);
  881.             reginput++;
  882.             break;
  883.         case ANYBUT:
  884.              if (*reginput == '\0' || strchr(OPERAND(scan), *reginput) != NULL)
  885.                 return(0);
  886.             reginput++;
  887.             break;
  888.         case NOTHING:
  889.             break;
  890.         case BACK:
  891.             break;
  892.         case OPEN+1:
  893.         case OPEN+2:
  894.         case OPEN+3:
  895.         case OPEN+4:
  896.         case OPEN+5:
  897.         case OPEN+6:
  898.         case OPEN+7:
  899.         case OPEN+8:
  900.         case OPEN+9: {
  901.                 register int no;
  902.                 register char *save;
  903.  
  904.                 no = OP(scan) - OPEN;
  905.                 save = reginput;
  906.  
  907.                 if (regmatch(next)) {
  908.                     /*
  909.                      * Don't set startp if some later
  910.                      * invocation of the same parentheses
  911.                      * already has.
  912.                      */
  913.                     if (regstartp[no] == NULL)
  914.                         regstartp[no] = save;
  915.                     return(1);
  916.                 } else
  917.                     return(0);
  918.             }
  919.             /* NOTREACHED */
  920.             break;
  921.         case CLOSE+1:
  922.         case CLOSE+2:
  923.         case CLOSE+3:
  924.         case CLOSE+4:
  925.         case CLOSE+5:
  926.         case CLOSE+6:
  927.         case CLOSE+7:
  928.         case CLOSE+8:
  929.         case CLOSE+9: {
  930.                 register int no;
  931.                 register char *save;
  932.  
  933.                 no = OP(scan) - CLOSE;
  934.                 save = reginput;
  935.  
  936.                 if (regmatch(next)) {
  937.                     /*
  938.                      * Don't set endp if some later
  939.                      * invocation of the same parentheses
  940.                      * already has.
  941.                      */
  942.                     if (regendp[no] == NULL)
  943.                         regendp[no] = save;
  944.                     return(1);
  945.                 } else
  946.                     return(0);
  947.             }
  948.             /* NOTREACHED */
  949.             break;
  950.         case BRANCH: {
  951.                 register char *save;
  952.  
  953.                 if (OP(next) != BRANCH)        /* No choice. */
  954.                     next = OPERAND(scan);    /* Avoid recursion. */
  955.                 else {
  956.                     do {
  957.                         save = reginput;
  958.                         if (regmatch(OPERAND(scan)))
  959.                             return(1);
  960.                         reginput = save;
  961.                         scan = regnext(scan);
  962.                     } while (scan != NULL && OP(scan) == BRANCH);
  963.                     return(0);
  964.                     /* NOTREACHED */
  965.                 }
  966.             }
  967.             /* NOTREACHED */
  968.             break;
  969.         case STAR:
  970.         case PLUS: {
  971.                 register char nextch;
  972.                 register int no;
  973.                 register char *save;
  974.                 register int min;
  975.  
  976.                 /*
  977.                  * Lookahead to avoid useless match attempts
  978.                  * when we know what character comes next.
  979.                  */
  980.                 nextch = '\0';
  981.                 if (OP(next) == EXACTLY)
  982.                     nextch = *OPERAND(next);
  983.                 min = (OP(scan) == STAR) ? 0 : 1;
  984.                 save = reginput;
  985.                 no = regrepeat(OPERAND(scan));
  986.                 while (no >= min) {
  987.                     /* If it could work, try it. */
  988.                     if (nextch == '\0' || *reginput == nextch)
  989.                         if (regmatch(next))
  990.                             return(1);
  991.                     /* Couldn't or didn't -- back up. */
  992.                     no--;
  993.                     reginput = save + no;
  994.                 }
  995.                 return(0);
  996.             }
  997.             /* NOTREACHED */
  998.             break;
  999.         case END:
  1000.             return(1);    /* Success! */
  1001.             /* NOTREACHED */
  1002.             break;
  1003.         default:
  1004.             regerror("memory corruption");
  1005.             return(0);
  1006.             /* NOTREACHED */
  1007.             break;
  1008.         }
  1009.  
  1010.         scan = next;
  1011.     }
  1012.  
  1013.     /*
  1014.      * We get here only if there's trouble -- normally "case END" is
  1015.      * the terminating point.
  1016.      */
  1017.     regerror("corrupted pointers");
  1018.     return(0);
  1019. }
  1020.  
  1021. /*
  1022.  - regrepeat - repeatedly match something simple, report how many
  1023.  */
  1024. static int
  1025. regrepeat(p)
  1026. char *p;
  1027. {
  1028.     register int count = 0;
  1029.     register char *scan;
  1030.     register char *opnd;
  1031.  
  1032.     scan = reginput;
  1033.     opnd = OPERAND(p);
  1034.     switch (OP(p)) {
  1035.     case ANY:
  1036.         count = strlen(scan);
  1037.         scan += count;
  1038.         break;
  1039.     case EXACTLY:
  1040.         while (*opnd == *scan) {
  1041.             count++;
  1042.             scan++;
  1043.         }
  1044.         break;
  1045.     case ANYOF:
  1046.         while (*scan != '\0' && strchr(opnd, *scan) != NULL) {
  1047.             count++;
  1048.             scan++;
  1049.         }
  1050.         break;
  1051.     case ANYBUT:
  1052.         while (*scan != '\0' && strchr(opnd, *scan) == NULL) {
  1053.             count++;
  1054.             scan++;
  1055.         }
  1056.         break;
  1057.     default:        /* Oh dear.  Called inappropriately. */
  1058.         regerror("internal foulup");
  1059.         count = 0;    /* Best compromise. */
  1060.         break;
  1061.     }
  1062.     reginput = scan;
  1063.  
  1064.     return(count);
  1065. }
  1066.  
  1067. /*
  1068.  - regnext - dig the "next" pointer out of a node
  1069.  */
  1070. static char *
  1071. regnext(p)
  1072. register char *p;
  1073. {
  1074.     register int offset;
  1075.  
  1076.     if (p == ®dummy)
  1077.         return(NULL);
  1078.  
  1079.     offset = NEXT(p);
  1080.     if (offset == 0)
  1081.         return(NULL);
  1082.  
  1083.     if (OP(p) == BACK)
  1084.         return(p-offset);
  1085.     else
  1086.         return(p+offset);
  1087. }
  1088.  
  1089. #ifdef DEBUG
  1090.  
  1091. STATIC char *regprop();
  1092.  
  1093. /*
  1094.  - regdump - dump a regexp onto stdout in vaguely comprehensible form
  1095.  */
  1096. void
  1097. regdump(r)
  1098. regexp *r;
  1099. {
  1100.     register char *s;
  1101.     register char op = EXACTLY;    /* Arbitrary non-END op. */
  1102.     register char *next;
  1103.     extern char *strchr();
  1104.  
  1105.  
  1106.     s = r->program + 1;
  1107.     while (op != END) {    /* While that wasn't END last time... */
  1108.         op = OP(s);
  1109.         printf("%2d%s", s-r->program, regprop(s));    /* Where, what. */
  1110.         next = regnext(s);
  1111.         if (next == NULL)        /* Next ptr. */
  1112.             printf("(0)");
  1113.         else 
  1114.             printf("(%d)", (s-r->program)+(next-s));
  1115.         s += 3;
  1116.         if (op == ANYOF || op == ANYBUT || op == EXACTLY) {
  1117.             /* Literal string, where present. */
  1118.             while (*s != '\0') {
  1119.                 putchar(*s);
  1120.                 s++;
  1121.             }
  1122.             s++;
  1123.         }
  1124.         putchar('\n');
  1125.     }
  1126.  
  1127.     /* Header fields of interest. */
  1128.     if (r->regstart != '\0')
  1129.         printf("start `%c' ", r->regstart);
  1130.     if (r->reganch)
  1131.         printf("anchored ");
  1132.     if (r->regmust != NULL)
  1133.         printf("must have \"%s\"", r->regmust);
  1134.     printf("\n");
  1135. }
  1136.  
  1137. /*
  1138.  - regprop - printable representation of opcode
  1139.  */
  1140. static char *
  1141. regprop(op)
  1142. char *op;
  1143. {
  1144.     register char *p;
  1145.     static char buf[50];
  1146.  
  1147.     (void) strcpy(buf, ":");
  1148.  
  1149.     switch (OP(op)) {
  1150.     case BOL:
  1151.         p = "BOL";
  1152.         break;
  1153.     case EOL:
  1154.         p = "EOL";
  1155.         break;
  1156.     case ANY:
  1157.         p = "ANY";
  1158.         break;
  1159.     case ANYOF:
  1160.         p = "ANYOF";
  1161.         break;
  1162.     case ANYBUT:
  1163.         p = "ANYBUT";
  1164.         break;
  1165.     case BRANCH:
  1166.         p = "BRANCH";
  1167.         break;
  1168.     case EXACTLY:
  1169.         p = "EXACTLY";
  1170.         break;
  1171.     case NOTHING:
  1172.         p = "NOTHING";
  1173.         break;
  1174.     case BACK:
  1175.         p = "BACK";
  1176.         break;
  1177.     case END:
  1178.         p = "END";
  1179.         break;
  1180.     case OPEN+1:
  1181.     case OPEN+2:
  1182.     case OPEN+3:
  1183.     case OPEN+4:
  1184.     case OPEN+5:
  1185.     case OPEN+6:
  1186.     case OPEN+7:
  1187.     case OPEN+8:
  1188.     case OPEN+9:
  1189.         sprintf(buf+strlen(buf), "OPEN%d", OP(op)-OPEN);
  1190.         p = NULL;
  1191.         break;
  1192.     case CLOSE+1:
  1193.     case CLOSE+2:
  1194.     case CLOSE+3:
  1195.     case CLOSE+4:
  1196.     case CLOSE+5:
  1197.     case CLOSE+6:
  1198.     case CLOSE+7:
  1199.     case CLOSE+8:
  1200.     case CLOSE+9:
  1201.         sprintf(buf+strlen(buf), "CLOSE%d", OP(op)-CLOSE);
  1202.         p = NULL;
  1203.         break;
  1204.     case STAR:
  1205.         p = "STAR";
  1206.         break;
  1207.     case PLUS:
  1208.         p = "PLUS";
  1209.         break;
  1210.     default:
  1211.         regerror("corrupted opcode");
  1212.         break;
  1213.     }
  1214.     if (p != NULL)
  1215.         (void) strcat(buf, p);
  1216.     return(buf);
  1217. }
  1218. #endif
  1219.  
  1220. /*
  1221.  * The following is provided for those people who do not have strcspn() in
  1222.  * their C libraries.  They should get off their butts and do something
  1223.  * about it; at least one public-domain implementation of those (highly
  1224.  * useful) string routines has been published on Usenet.
  1225.  */
  1226. #ifdef STRCSPN
  1227. /*
  1228.  * strcspn - find length of initial segment of s1 consisting entirely
  1229.  * of characters not from s2
  1230.  */
  1231.  
  1232. static int
  1233. strcspn(s1, s2)
  1234. char *s1;
  1235. char *s2;
  1236. {
  1237.     register char *scan1;
  1238.     register char *scan2;
  1239.     register int count;
  1240.  
  1241.     count = 0;
  1242.     for (scan1 = s1; *scan1 != '\0'; scan1++) {
  1243.         for (scan2 = s2; *scan2 != '\0';)    /* ++ moved down. */
  1244.             if (*scan1 == *scan2++)
  1245.                 return(count);
  1246.         count++;
  1247.     }
  1248.     return(count);
  1249. }
  1250. #endif
  1251. @
  1252.